
// Definition for a binary tree node.
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
#include <algorithm>
using namespace std;
class Solution
{
public:
    int __helper(TreeNode *root, int &res)
    {
        if (!root)
            return 0;
        // 获取最长一条边
        int left = __helper(root->left, res);
        int right = __helper(root->right, res);
        // 计算更新答案 对于每个节点都是 自己的val+左边最长边+右边最长边
        res = max(root->val + left + right, res);
        // 只返回最长边 如果左右最长加自己是<=0的就返回 0
        return max(root->val + max(max(left, right), 0), 0);
    }
    int maxPathSum(TreeNode *root)
    {
        int res = INT_MIN;
        __helper(root, res);
        return res;
    }
};